UVa/10482 - The candyman can/10482.4.cpp

   1 /*
   2   Problem: 10482 - The Candyman can
   3   (UVa Online Judge)
   4
   5   Andrés Mejía-Posada
   6
   7   ¡Accepted!
   8  */
   9 #include <iostream>
  10 #include <vector>
  11 #include <algorithm>
  12 using namespace std;
  13
  14 const int SIZE = 40, MAXN = 32;
  15
  16 /*
  17   dp[i][a][b] = verdadero si puedo repartir las primeras
  18   i monedas en tres grupos tales que el grupo con mayor peso
  19   tenga a unidades más que el grupo con menos peso & el grupo
  20   de la mitad tenga b unidades más que el grupo con menos peso
  21  */
  22 bool dp[MAXN][SIZE+1][SIZE+1];
  23
  24 int main(){
  25   int Casos;
  26   scanf("%d", &Casos);
  27   for (int C=1; C<=Casos; C++){
  28     int n, sum = 0;
  29     scanf("%d", &n);
  30     vector<int> w(n);
  31     for (int i=0; i<n; ++i){
  32       scanf("%d", &w[i]);
  33       sum += w[i];
  34     }
  35
  36     sum = min(sum, SIZE);
  37
  38     for (int i=0; i<n; ++i)
  39       for (int a=0; a<=sum; ++a)
  40         for (int b=0; b<=sum; ++b)
  41           dp[i][a][b] = false;
  42
  43
  44     dp[0][w[0]][0] = true;
  45     for (int i=0; i<n-1; ++i)
  46       for (int a=0; a<=sum; ++a)
  47         for (int b=0; b<=sum; ++b)
  48           if (dp[i][a][b])
  49             for (int j=0; j<3; ++j){
  50               vector<int> t(3);
  51               t[0] = a, t[1] = b, t[2] = 0;
  52               t[j] += w[i+1];
  53               sort(t.begin(), t.end());
  54               if (t[2] - t[0] <= sum){
  55                 dp[i+1][t[2] - t[0]][t[1] - t[0]] = true;
  56               }
  57             }
  58
  59     int answer = -1;
  60     for (int a=0; a<=sum && answer == -1; ++a)
  61       for (int b=0; b<=a && answer == -1; ++b)
  62         if (dp[n-1][a][b]){
  63           answer = a;
  64         }
  65
  66     printf("Case %d: %d\n", C, answer);
  67   }
  68   return 0;
  69 }
  70
  71